⟸ pàgina anterior ⟸

Exercici 8 (Tasca 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages))

Són computables?

Per a cadascuna de les següents funcions f, determineu si f és computable, si \mathrm{Dom}(f)=\mathbb{N} (és a dir, si f és total), i quina és \mathrm{Im}(f):

1. f(x)=\begin{cases} 1 &\text{si } \exists n\ M_n(x)\!\downarrow\\ \uparrow &\text{altrament}\end{cases}
2. f(x)=\begin{cases} 1 &\text{si } \forall n\ M_n(x)\!\downarrow\\ \uparrow &\text{altrament}\end{cases}
3. f(x)=\begin{cases} 1 &\text{si } \exists n\ M_x(n)\!\downarrow\\ \uparrow &\text{altrament}\end{cases}
4. f(x)=\begin{cases} 1 &\text{si } \forall n\ M_x(n)\!\downarrow\\ \uparrow &\text{altrament}\end{cases}